{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Title: #螺旋遍历二维数组"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Difficulty: #Easy"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Category Title: #Algorithms"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Tag Slug: #array #matrix #simulation"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Name Translated: #数组 #矩阵 #模拟"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution Name: spiralArray"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Title: #螺旋遍历二维数组"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Content:\n",
    "<p>给定一个二维数组 <code>array</code>，请返回「<strong>螺旋遍历</strong>」该数组的结果。</p>\n",
    "\n",
    "<p><strong>螺旋遍历</strong>：从左上角开始，按照 <strong>向右</strong>、<strong>向下</strong>、<strong>向左</strong>、<strong>向上</strong> 的顺序 <strong>依次</strong> 提取元素，然后再进入内部一层重复相同的步骤，直到提取完所有元素。</p>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>示例 1：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>array = [[1,2,3],[8,9,4],[7,6,5]]\n",
    "<strong>输出：</strong>[1,2,3,4,5,6,7,8,9]\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 2：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>array &nbsp;= [[1,2,3,4],[12,13,14,5],[11,16,15,6],[10,9,8,7]]\n",
    "<strong>输出：</strong>[1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16]\n",
    "</pre>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>限制：</strong></p>\n",
    "\n",
    "<ul>\n",
    "\t<li><code>0 &lt;= array.length &lt;= 100</code></li>\n",
    "\t<li><code>0 &lt;= array[i].length &lt;= 100</code></li>\n",
    "</ul>\n",
    "\n",
    "<p>注意：本题与主站 54 题相同：<a href=\"https://leetcode-cn.com/problems/spiral-matrix/\">https://leetcode-cn.com/problems/spiral-matrix/</a></p>\n",
    "\n",
    "<p>&nbsp;</p>\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Description: [shun-shi-zhen-da-yin-ju-zhen-lcof](https://leetcode.cn/problems/shun-shi-zhen-da-yin-ju-zhen-lcof/description/)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solutions: [shun-shi-zhen-da-yin-ju-zhen-lcof](https://leetcode.cn/problems/shun-shi-zhen-da-yin-ju-zhen-lcof/solutions/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "test_cases = ['[[1,2,3],[4,5,6],[7,8,9]]', '[[1,2,3,4],[12,13,14,5],[11,16,15,6],[10,9,8,7]]']"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def spiralArray(self, array: List[List[int]]) -> List[int]:\n",
    "        if not array or not array[0] :\n",
    "            return array\n",
    "        row, column = len(array), len(array[0])\n",
    "        left, top, right, bottom = 0, 0, column-1, row-1\n",
    "        ans = []\n",
    "        while left <= right and top <= bottom :\n",
    "            for x in range(left, right+1):\n",
    "                ans.append(array[top][x])\n",
    "            for x in range(top+1, bottom+1):\n",
    "                ans.append(array[x][right])\n",
    "            if left < right and top < bottom :\n",
    "                for x in range(right-1, left, -1):\n",
    "                    ans.append(array[bottom][x])\n",
    "                for x in range(bottom, top, -1):\n",
    "                    ans.append(array[x][left])\n",
    "            left, top, right, bottom = left + 1, top + 1, right - 1 , bottom - 1\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def spiralArray(self, array: List[List[int]]) -> List[int]:\n",
    "        res = []\n",
    "        h = len(array)\n",
    "        if h == 0:\n",
    "            return res\n",
    "        w = len(array[0])\n",
    "        for offset in range(min(h, w)//2):\n",
    "            for i in range(offset, w-1-offset):\n",
    "                res.append(array[offset][i])\n",
    "            for i in range(offset, h-1-offset):\n",
    "                res.append(array[i][w-1-offset])\n",
    "            for i in range(w-1-offset, offset, -1):\n",
    "                res.append(array[h-1-offset][i])\n",
    "            for i in range(h-1-offset, offset, -1):\n",
    "                res.append(array[i][offset])\n",
    "        if h >= w:\n",
    "            if w%2 == 1:\n",
    "                for i in range(w//2, h-w//2):\n",
    "                    res.append(array[i][w//2])\n",
    "        else:\n",
    "            if h%2 == 1:\n",
    "                for i in range(h//2, w-h//2):\n",
    "                    res.append(array[h//2][i])\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def spiralArray(self, array: List[List[int]]) -> List[int]:\n",
    "        if not array or not array[0]:\n",
    "            return []\n",
    "        \n",
    "        order = []\n",
    "        rows, columns = len(array), len(array[0])\n",
    "        left, right, top, bottom = 0, columns-1, 0, rows-1\n",
    "        while left <= right and top <= bottom:\n",
    "            for column in range(left, right+1): # 注意这里left==right时，只执行一次循环\n",
    "                order.append(array[top][column])\n",
    "            for row in range(top+1, bottom+1):  # 注意这里当top==bottom时，不执行循环\n",
    "                order.append(array[row][right])\n",
    "            if left < right and top < bottom:\n",
    "                for column in range(right-1, left, -1):\n",
    "                    order.append(array[bottom][column])\n",
    "                for row in range(bottom, top, -1):\n",
    "                    order.append(array[row][left])\n",
    "            left, right, top, bottom = left+1, right-1, top+1, bottom-1\n",
    "        return order"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def spiralArray(self, array: List[List[int]]) -> List[int]:\n",
    "        if not array or not array[0]:\n",
    "            return list()\n",
    "        \n",
    "        rows, columns = len(array), len(array[0])\n",
    "        visited = [[False] * columns for _ in range(rows)]\n",
    "        total = rows * columns\n",
    "        order = [0] * total\n",
    "\n",
    "        directions = [[0, 1], [1, 0], [0, -1], [-1, 0]]\n",
    "        row, column = 0, 0\n",
    "        directionIndex = 0\n",
    "        for i in range(total):\n",
    "            order[i] = array[row][column]\n",
    "            visited[row][column] = True\n",
    "            nextRow, nextColumn = row + directions[directionIndex][0], column + directions[directionIndex][1]\n",
    "            if not (0 <= nextRow < rows and 0 <= nextColumn < columns and not visited[nextRow][nextColumn]):\n",
    "                directionIndex = (directionIndex + 1) % 4\n",
    "            row += directions[directionIndex][0]\n",
    "            column += directions[directionIndex][1]\n",
    "        return order"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def spiralArray(self, array: List[List[int]]) -> List[int]:\n",
    "        if not array:\n",
    "            return []\n",
    "        top, right, left, bottom = 0, len(array[0]) - 1, 0 , len(array) - 1\n",
    "        ans = []\n",
    "        while True:\n",
    "            for i in range(left, right + 1):\n",
    "                ans.append(array[top][i])\n",
    "            top += 1\n",
    "            if top > bottom:\n",
    "                break\n",
    "            for i in range(top, bottom + 1):\n",
    "                ans.append(array[i][right])\n",
    "            right -= 1\n",
    "            if left > right:\n",
    "                break\n",
    "            for i in range(right, left - 1, -1):\n",
    "                ans.append(array[bottom][i])\n",
    "            bottom -= 1\n",
    "            if bottom < top:\n",
    "                break\n",
    "            for i in range(bottom, top -1, -1):\n",
    "                ans.append(array[i][left])\n",
    "            left += 1\n",
    "            if left > right:\n",
    "                break\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def spiralArray(self, array: List[List[int]]) -> List[int]:\n",
    "        if not array: return []\n",
    "        ans = []\n",
    "        l, r, t, b = 0, len(array[0]) - 1, 0, len(array) - 1\n",
    "        while True:\n",
    "            for i in range(l, r + 1): ans.append(array[t][i])\n",
    "            t += 1\n",
    "            if t > b: break\n",
    "            for i in range(t, b + 1): ans.append(array[i][r])\n",
    "            r -= 1\n",
    "            if l > r: break\n",
    "            for i in range(r, l - 1, -1): ans.append(array[b][i])\n",
    "            b -= 1\n",
    "            if t > b: break\n",
    "            for i in range(b, t - 1, -1): ans.append(array[i][l])\n",
    "            l += 1\n",
    "            if l > r: break\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def spiralArray(self, array: List[List[int]]) -> List[int]:\n",
    "        res = []\n",
    "        if array is None or len(array) == 0:\n",
    "            return res\n",
    "        \n",
    "        m = len(array)\n",
    "        n = len(array[0])\n",
    "\n",
    "        r1, c1 = 0, 0\n",
    "        r2, c2 = m - 1, n - 1\n",
    "\n",
    "        while r1 <= r2 and c1 <= c2:\n",
    "            if r1 == r2:\n",
    "                for c in range(c1, c2 + 1):\n",
    "                    res.append(array[r1][c])\n",
    "            elif c1 == c2:\n",
    "                for r in range(r1, r2 + 1):\n",
    "                    res.append(array[r][c1])\n",
    "            else:\n",
    "                for c in range(c1, c2):\n",
    "                    res.append(array[r1][c])\n",
    "                \n",
    "                for r in range(r1, r2):\n",
    "                    res.append(array[r][c2])\n",
    "\n",
    "                for c in range(c2, c1, -1):\n",
    "                    res.append(array[r2][c])\n",
    "                \n",
    "                for r in range(r2, r1, -1):\n",
    "                    res.append(array[r][c1])\n",
    "            \n",
    "            r1 += 1\n",
    "            c1 += 1\n",
    "            r2 -= 1\n",
    "            c2 -= 1\n",
    "        \n",
    "        return res\n",
    "\n",
    "\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def spiralArray(self, array: List[List[int]]) -> List[int]:\n",
    "        \n",
    "        m = len(array)\n",
    "        if m == 0 :\n",
    "            return []\n",
    "        n = len(array[0])\n",
    "\n",
    "        result = []\n",
    "        loop = min(m,n)//2\n",
    "        mid = min(m,n)//2\n",
    "        startx,starty = 0,0\n",
    "\n",
    "        for offset in range(1,loop + 1):\n",
    "            #左到右\n",
    "            for i in range(startx,n-offset):\n",
    "                result.append(array[startx][i])\n",
    "\n",
    "            #上到下\n",
    "            for i in range(starty,m - offset):\n",
    "                result.append(array[i][n - offset])\n",
    "\n",
    "            #右到左\n",
    "            for i in range(n - offset,startx,-1):\n",
    "                result.append(array[m - offset][i])\n",
    "\n",
    "            #下到上\n",
    "            for i in range(m - offset,starty,-1):\n",
    "                result.append(array[i][starty])\n",
    "\n",
    "            startx = startx + 1\n",
    "            starty = starty + 1\n",
    "\n",
    "        if min(m,n) % 2 == 1:\n",
    "            if m > n:\n",
    "                for i in range(mid,mid + m - n +1):\n",
    "                    result.append(array[i][mid])\n",
    "            else:\n",
    "                for i in range(mid,mid + n - m + 1):\n",
    "                    result.append(array[mid][i])\n",
    "        \n",
    "        return result\n",
    "\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def spiralArray(self, array: List[List[int]]) -> List[int]:\n",
    "        if array == []:\n",
    "            return []\n",
    "        m = len(array)\n",
    "        n = len(array[0])\n",
    "        left, right, top, bottom = 0, n-1, 0, m-1\n",
    "        ans = [0] * m * n\n",
    "        num = 0\n",
    "        while left <= right and top <= bottom:\n",
    "            for col in range(left, right+1):\n",
    "                ans[num] = array[top][col]\n",
    "                num += 1\n",
    "            for row in range(top+1, bottom+1):\n",
    "                ans[num] = array[row][right]\n",
    "                num += 1\n",
    "            if left < right and top < bottom:\n",
    "                for col in range(right-1, left, -1):\n",
    "                    ans[num] = array[bottom][col]\n",
    "                    num += 1\n",
    "                for row in range(bottom, top, -1):\n",
    "                    ans[num] = array[row][left]\n",
    "                    num += 1\n",
    "            left += 1\n",
    "            right -= 1\n",
    "            top += 1\n",
    "            bottom -= 1\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def spiralArray(self, array: List[List[int]]) -> List[int]:\n",
    "        if not array:\n",
    "            return array\n",
    "        row = len(array)\n",
    "        column = len(array[0])\n",
    "        res = []\n",
    "        left, right, top, bottom = 0, column - 1, 0 , row - 1\n",
    "        while left <= right and top <= bottom:\n",
    "            for column in range(left, right + 1):\n",
    "                res.append(array[top][column])\n",
    "            for row in range(top + 1, bottom + 1):\n",
    "                res.append(array[row][right])\n",
    "            if left < right and top < bottom:\n",
    "                for column in range(right - 1, left, -1):\n",
    "                    res.append(array[bottom][column])\n",
    "                for row in range(bottom, top, -1):\n",
    "                    res.append(array[row][left])\n",
    "            left, right, top, bottom = left + 1, right - 1, top + 1, bottom - 1\n",
    "        return res \n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "        # for (di, dj) in direction:\n",
    "        #     i += di\n",
    "        #     j += dj\n",
    "        #     if 0 <= i < len(array) and 0 <= j < len(array[0]) and num[i][j] == 0:\n",
    "        #         num[i][j] += 1\n",
    "        #         res = res.append(array[i][j])\n",
    "        #         break\n",
    "        #     return res\n",
    "            \n",
    "            \n",
    "            \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def spiralArray(self, array: List[List[int]]) -> List[int]:\n",
    "        res = []\n",
    "        h = len(array)\n",
    "        if h == 0:\n",
    "            return res\n",
    "        w = len(array[0])\n",
    "        for offset in range(min(h, w)//2):\n",
    "            for i in range(offset, w-1-offset):\n",
    "                res.append(array[offset][i])\n",
    "            for i in range(offset, h-1-offset):\n",
    "                res.append(array[i][w-1-offset])\n",
    "            for i in range(w-1-offset, offset, -1):\n",
    "                res.append(array[h-1-offset][i])\n",
    "            for i in range(h-1-offset, offset, -1):\n",
    "                res.append(array[i][offset])\n",
    "        if h >= w:\n",
    "            if w%2 == 1:\n",
    "                for i in range(w//2, h-w//2):\n",
    "                    res.append(array[i][w//2])\n",
    "        else:\n",
    "            if h%2 == 1:\n",
    "                for i in range(h//2, w-h//2):\n",
    "                    res.append(array[h//2][i])\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def spiralArray(self, array: List[List[int]]) -> List[int]:\n",
    "        if not array or not array[0]:\n",
    "            return []\n",
    "        \n",
    "        i, j = len(array), len(array[0])\n",
    "\n",
    "        ret = []\n",
    "\n",
    "        left, right, top, bottom = 0, j - 1, 0, i-1\n",
    "        while left <= right and top <= bottom:\n",
    "            for column in range(left, right + 1):\n",
    "                ret.append(array[top][column])\n",
    "            # 注意已经遍历过的\n",
    "            for row in range(top + 1, bottom + 1):\n",
    "                ret.append(array[row][right])\n",
    "            \n",
    "            if left < right and top < bottom:\n",
    "                for column in range(right -1, left, -1):\n",
    "                    ret.append(array[bottom][column])\n",
    "                for row in range(bottom, top,  -1):\n",
    "                    ret.append(array[row][left])\n",
    "            \n",
    "            left, right, top, bottom = left + 1, right - 1, top + 1, bottom -1\n",
    "        \n",
    "        return ret\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def spiralArray(self, array: List[List[int]]) -> List[int]:\n",
    "        res = []\n",
    "        if not array:\n",
    "            return []\n",
    "        \n",
    "        l = 0\n",
    "        r = len(array[0]) - 1\n",
    "        t = 0\n",
    "        b = len(array) - 1\n",
    "        print(l,r,b,t)\n",
    "        while True:\n",
    "            for i in range(l,r+1):\n",
    "                res.append(array[t][i])\n",
    "            t += 1\n",
    "            if t>b :\n",
    "                break\n",
    "            for i in range(t,b+1):\n",
    "                res.append(array[i][r])\n",
    "            r -= 1\n",
    "            if l>r:\n",
    "                break\n",
    "            for i in range(r,l-1, -1):\n",
    "                res.append(array[b][i])\n",
    "            b -= 1\n",
    "            if t>b:\n",
    "                break\n",
    "            for i in range(b,t-1, -1):\n",
    "                res.append(array[i][l])\n",
    "            l += 1\n",
    "            if l>r:\n",
    "                break\n",
    "            \n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def spiralArray(self, array: list[list[int]]) -> list[int]:\n",
    "        if not array:\n",
    "            return []\n",
    "\n",
    "        x, y = len(array[0]), len(array)  # x应为列数，y应为行数\n",
    "        left, right, top, bottom = 0, x - 1, 0, y - 1  # 定义边界\n",
    "        direction = 0  # 0: right, 1: down, 2: left, 3: up\n",
    "        result = []\n",
    "\n",
    "        while left <= right and top <= bottom:\n",
    "            if direction == 0:  # 从左到右\n",
    "                for i in range(left, right + 1):\n",
    "                    result.append(array[top][i])\n",
    "                top += 1\n",
    "            elif direction == 1:  # 从上到下\n",
    "                for i in range(top, bottom + 1):\n",
    "                    result.append(array[i][right])\n",
    "                right -= 1\n",
    "            elif direction == 2:  # 从右到左\n",
    "                for i in range(right, left - 1, -1):\n",
    "                    result.append(array[bottom][i])\n",
    "                bottom -= 1\n",
    "            elif direction == 3:  # 从下到上\n",
    "                for i in range(bottom, top - 1, -1):\n",
    "                    result.append(array[i][left])\n",
    "                left += 1\n",
    "            direction = (direction + 1) % 4  # 更新方向\n",
    "\n",
    "        return result"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def spiralArray(self, nums: List[List[int]]) -> List[int]:\n",
    "\n",
    "        if not nums:\n",
    "            return []\n",
    "\n",
    "        idx = 1\n",
    "        cnt = len(nums) * len(nums[0])\n",
    "        res = []\n",
    "\n",
    "        up = 0\n",
    "        bottom = len(nums) - 1\n",
    "\n",
    "        left = 0\n",
    "        right = len(nums[0]) - 1\n",
    "\n",
    "        while idx <= cnt:\n",
    "            i = left\n",
    "            while i <= right and idx <= cnt:\n",
    "                res.append(nums[up][i])\n",
    "                idx += 1\n",
    "                i += 1\n",
    "            up += 1\n",
    "\n",
    "            j = up\n",
    "            while j <= bottom and idx <= cnt:\n",
    "                res.append(nums[j][right])\n",
    "                idx += 1\n",
    "                j += 1\n",
    "            right -= 1\n",
    "\n",
    "            i = right\n",
    "            while i >= left and idx <= cnt:\n",
    "                res.append(nums[bottom][i])\n",
    "                idx += 1\n",
    "                i -= 1\n",
    "            bottom -= 1\n",
    "\n",
    "            j = bottom\n",
    "            while j >= up and idx <= cnt:\n",
    "                res.append(nums[j][left])\n",
    "                idx += 1\n",
    "                j -= 1\n",
    "            left += 1\n",
    "\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def spiralArray(self, array: List[List[int]]) -> List[int]:\n",
    "        if not array:\n",
    "            return []\n",
    "        l,r,t,b,res = 0,len(array[0])-1,0,len(array)-1,[]\n",
    "        while True:\n",
    "            for i in range(l,r+1):\n",
    "                res.append(array[t][i])\n",
    "            t += 1\n",
    "            if t>b: break\n",
    "\n",
    "            for i in range(t,b+1):\n",
    "                res.append(array[i][r])\n",
    "            r -= 1\n",
    "            if l>r: break\n",
    "\n",
    "            for i in range(r,l-1,-1):\n",
    "                res.append(array[b][i])\n",
    "            b -= 1\n",
    "            if t>b: break\n",
    "\n",
    "            for i in range(b,t-1,-1):\n",
    "                res.append(array[i][l])\n",
    "            l += 1\n",
    "            if l>r: break\n",
    "\n",
    "        return res\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def spiralArray(self, array: List[List[int]]) -> List[int]:\n",
    "        if not array: return []\n",
    "        left, right, upper, lower, res = 0, len(array[0]) - 1, 0, len(array) - 1, []\n",
    "        while True:\n",
    "            for i in range(left, right + 1): res.append(array[upper][i])\n",
    "            upper += 1\n",
    "            if upper > lower: break\n",
    "            for i in range(upper, lower + 1): res.append(array[i][right])\n",
    "            right -= 1\n",
    "            if left > right: break\n",
    "            for i in range(right, left - 1, -1): res.append(array[lower][i])\n",
    "            lower -= 1\n",
    "            if upper > lower: break\n",
    "            for i in range(lower, upper - 1, -1): res.append(array[i][left])\n",
    "            left += 1\n",
    "            if left > right: break\n",
    "        return res\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def spiralArray(self, array: List[List[int]]) -> List[int]:\n",
    "        if not len(array):\n",
    "            return []\n",
    "        dir = [[0,1],[1, 0],[0,-1],[-1,0]]\n",
    "        state = 0\n",
    "        x = 0\n",
    "        y = -1\n",
    "        ans = []\n",
    "        n = len(array)\n",
    "        m = len(array[0])\n",
    "        for i in range(n * m):\n",
    "            next_x, next_y = x + dir[state][0], y + dir[state][1]\n",
    "            if 0 <= next_x < n and 0 <= next_y < m and array[next_x][next_y] != \"\":\n",
    "                # print(\"go\")\n",
    "                ans.append(array[next_x][next_y])\n",
    "                array[next_x][next_y] = \"\"\n",
    "                x, y = next_x, next_y\n",
    "            else:\n",
    "                # print(\"turn\")\n",
    "                state = (state + 1) % 4\n",
    "                next_x, next_y = x + dir[state][0], y + dir[state][1]\n",
    "                if 0 <= next_x < n and 0 <= next_y < m and array[next_x][next_y] != \"\":\n",
    "                    ans.append(array[next_x][next_y])\n",
    "                    array[next_x][next_y] = \"\"\n",
    "                    x, y = next_x, next_y\n",
    "                    # print(\"!\")\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def spiralArray(self, array: List[List[int]]) -> List[int]:\n",
    "        if not array:\n",
    "            return []\n",
    "        ans=[]\n",
    "        up=0\n",
    "        down=len(array)-1\n",
    "        left=0\n",
    "        right=len(array[0])-1\n",
    "        while True:\n",
    "            for i in range(left,right+1):\n",
    "                ans.append(array[up][i])\n",
    "            up+=1\n",
    "            if up>down:\n",
    "                break\n",
    "            for i in range(up,down+1):\n",
    "                ans.append(array[i][right])\n",
    "            right-=1\n",
    "            if left>right:\n",
    "                break\n",
    "            for i in range(right,left-1,-1):\n",
    "                ans.append(array[down][i])\n",
    "            down-=1\n",
    "            if up>down:\n",
    "                break\n",
    "            for i in range(down,up-1,-1):\n",
    "                ans.append(array[i][left])\n",
    "            left+=1\n",
    "            if left>right:\n",
    "                break\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def spiralArray(self, array: List[List[int]]) -> List[int]:\n",
    "        if not array: return []\n",
    "        l, r, t, b, res = 0, len(array[0]) - 1, 0, len(array) - 1, []\n",
    "        while True:\n",
    "            for i in range(l, r + 1): res.append(array[t][i]) # left to right\n",
    "            t += 1\n",
    "            if t > b: break\n",
    "            for i in range(t, b + 1): res.append(array[i][r]) # top to bottom\n",
    "            r -= 1\n",
    "            if l > r: break\n",
    "            for i in range(r, l - 1, -1): res.append(array[b][i]) # right to left\n",
    "            b -= 1\n",
    "            if t > b: break\n",
    "            for i in range(b, t - 1, -1): res.append(array[i][l]) # bottom to top\n",
    "            l += 1\n",
    "            if l > r: break\n",
    "        return res\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def spiralArray(self, array: List[List[int]]) -> List[int]:\n",
    "        if not array: return array\n",
    "        imin,imax,jmin,jmax,i,j = 0,len(array)-1,0,len(array[0])-1,0,0\n",
    "        lis = []\n",
    "        while True:\n",
    "            for x in range(jmin,jmax+1):\n",
    "                lis.append(array[imin][x])\n",
    "            imin += 1\n",
    "            if imin > imax:break\n",
    "            for x in range(imin,imax+1):\n",
    "                lis.append(array[x][jmax])\n",
    "            jmax -= 1\n",
    "            if jmax < jmin:break\n",
    "            for x in range(jmax,jmin-1,-1):\n",
    "                lis.append(array[imax][x])\n",
    "            imax -= 1\n",
    "            if imax < imin:break\n",
    "            for x in range(imax,imin-1,-1):\n",
    "                lis.append(array[x][jmin])\n",
    "            jmin  += 1 \n",
    "            if jmin > jmax:break\n",
    "        return lis           \n",
    "                \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def spiralArray(self, array: List[List[int]]) -> List[int]:\n",
    "        if not array: return []\n",
    "        l,r,t,b,res = 0, len(array[0])-1, 0, len(array)-1, []\n",
    "        while True:\n",
    "            for i in range(l, r+1):\n",
    "                res.append(array[t][i])\n",
    "            t += 1\n",
    "            if t > b: break\n",
    "            for i in range(t, b+1):\n",
    "                res.append(array[i][r])\n",
    "            r -= 1\n",
    "            if r < l:break\n",
    "            for i in range(r, l-1, -1):\n",
    "                res.append(array[b][i])\n",
    "            b -= 1\n",
    "            if b < t:break\n",
    "            for i in range(b, t-1, -1):\n",
    "                res.append(array[i][l])\n",
    "            l += 1\n",
    "            if l > r:break\n",
    "        return res\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def spiralArray(self, array: List[List[int]]) -> List[int]:\n",
    "        if not array:\n",
    "            return []\n",
    "        l = 0\n",
    "        r = len(array[0]) - 1\n",
    "        t = 0\n",
    "        b = len(array) - 1\n",
    "        res = []\n",
    "\n",
    "        while True:\n",
    "            #left to right\n",
    "            for i in range(l,r + 1):\n",
    "                res.append(array[t][i])\n",
    "            t += 1\n",
    "            if t > b:\n",
    "                break\n",
    "\n",
    "            #top to bottom\n",
    "            for i in range(t,b+1):\n",
    "                res.append(array[i][r])\n",
    "            r -= 1\n",
    "            if l > r:\n",
    "                break\n",
    "\n",
    "            #right to left\n",
    "            for i in range(r,l-1,-1):\n",
    "                res.append(array[b][i])\n",
    "            b -= 1\n",
    "            if t > b:\n",
    "                break\n",
    "\n",
    "            #bottom to top\n",
    "            for i in range(b,t-1,-1):\n",
    "                res.append(array[i][l])\n",
    "            l += 1\n",
    "            if l > r:\n",
    "                break\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def spiralArray(self, array: List[List[int]]) -> List[int]:\n",
    "        if len(array) == 0 or len(array[0]) == 0:\n",
    "            return []\n",
    "        m, n = len(array), len(array[0])\n",
    "        minNum = min(m, n)\n",
    "        ans = []\n",
    "        i = 0\n",
    "        while i < minNum // 2:\n",
    "            # 上行\n",
    "            for j in range(n - 2 * i - 1):\n",
    "                ans.append(array[i][i + j])\n",
    "            # 右列\n",
    "            for j in range(m - 2 * i - 1):\n",
    "                ans.append(array[i + j][n - i - 1])\n",
    "            # 下行\n",
    "            for j in range(n - 2 * i - 1):\n",
    "                ans.append(array[m - i - 1][n - i - j - 1])\n",
    "            # 左列\n",
    "            for j in range(m - 2 * i - 1):\n",
    "                ans.append(array[m - i - j - 1][i])\n",
    "            i += 1\n",
    "        if minNum % 2 == 1:\n",
    "            if minNum == m:\n",
    "                for j in range(n - 2 * i):\n",
    "                    ans.append(array[i][i + j])\n",
    "            else:\n",
    "                for j in range(m - 2 * i):\n",
    "                    ans.append(array[i + j][i])\n",
    "        return ans\n",
    "\n",
    "\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def spiralArray(self, array: List[List[int]]) -> List[int]:\n",
    "        if not len(array):\n",
    "            return []\n",
    "        dir = [[0,1],[1, 0],[0,-1],[-1,0]]\n",
    "        state = 0\n",
    "        x = 0\n",
    "        y = -1\n",
    "        ans = []\n",
    "        n = len(array)\n",
    "        m = len(array[0])\n",
    "        for i in range(n * m):\n",
    "            next_x, next_y = x + dir[state][0], y + dir[state][1]\n",
    "            if 0 <= next_x < n and 0 <= next_y < m and array[next_x][next_y] != \"\":\n",
    "                # print(\"go\")\n",
    "                ans.append(array[next_x][next_y])\n",
    "                array[next_x][next_y] = \"\"\n",
    "                x, y = next_x, next_y\n",
    "            else:\n",
    "                # print(\"turn\")\n",
    "                state = (state + 1) % 4\n",
    "                next_x, next_y = x + dir[state][0], y + dir[state][1]\n",
    "                if 0 <= next_x < n and 0 <= next_y < m and array[next_x][next_y] != \"\":\n",
    "                    ans.append(array[next_x][next_y])\n",
    "                    array[next_x][next_y] = \"\"\n",
    "                    x, y = next_x, next_y\n",
    "                    # print(\"!\")\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def spiralArray(self, array: List[List[int]]) -> List[int]:\n",
    "        if not array:return []\n",
    "        t,r,b,l,res=0,len(array[0])-1,len(array)-1,0,[]\n",
    "        while True:\n",
    "            for i in range(l,r+1):\n",
    "                res.append(array[t][i])\n",
    "            t=t+1\n",
    "            if t>b: break\n",
    "            for i in range(t,b+1):\n",
    "                res.append(array[i][r])\n",
    "            r=r-1\n",
    "            if l>r: break\n",
    "            for i in range(r,l-1,-1):\n",
    "                res.append(array[b][i])\n",
    "            b=b-1\n",
    "            if t>b: break\n",
    "            for i in range(b,t-1,-1):\n",
    "                res.append(array[i][l])\n",
    "            l=l+1\n",
    "            if l>r: break\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def spiralArray(self, array: List[List[int]]) -> List[int]:\n",
    "        if not array:\n",
    "            return []\n",
    "        lst = []\n",
    "        n = len(array)\n",
    "        m = len(array[0])\n",
    "        size = n * m\n",
    "        top = left = 0\n",
    "        bot = n - 1\n",
    "        right = m - 1\n",
    "        num = 1\n",
    "        while num <= size:\n",
    "            for i in range(left, right + 1):\n",
    "                lst.append(array[top][i])\n",
    "                num += 1\n",
    "            top += 1\n",
    "\n",
    "            if top > bot:\n",
    "                break\n",
    "\n",
    "            for i in range(top, bot + 1):\n",
    "                lst.append(array[i][right])\n",
    "                num += 1\n",
    "            right -= 1\n",
    "\n",
    "            if left > right:\n",
    "                break\n",
    "\n",
    "            for i in range(right, left - 1, -1):\n",
    "                lst.append(array[bot][i])\n",
    "                num += 1\n",
    "            bot -= 1\n",
    "\n",
    "            if top > bot:\n",
    "                break\n",
    "\n",
    "            for i in range(bot, top - 1, -1):\n",
    "                lst.append(array[i][left])\n",
    "                num += 1\n",
    "            left += 1\n",
    "\n",
    "            if left> right:\n",
    "                break\n",
    "        return lst\n",
    "\n",
    "# 和插入不同的点在于需要设置break的判断"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def spiralArray(self, array: List[List[int]]) -> List[int]:\n",
    "        if len(array)==0:return array\n",
    "        l,r,t,b=0,len(array[0])-1,0,len(array)-1\n",
    "        arrayA=[]\n",
    "        while l<=r and t<=b:\n",
    "            for i in range(l,r+1):\n",
    "                arrayA.append(array[t][i])\n",
    "            t+=1\n",
    "            if t>b:break\n",
    "            for i in range(t,b+1):\n",
    "                arrayA.append(array[i][r])\n",
    "            r-=1\n",
    "            if l>r: break\n",
    "            for i in range(r,l-1,-1):\n",
    "                arrayA.append(array[b][i])\n",
    "            b-=1\n",
    "            if t>b:break\n",
    "            for i in range(b,t-1,-1):\n",
    "                arrayA.append(array[i][l])\n",
    "            l+=1\n",
    "            if l>r:break\n",
    "        return arrayA\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def spiralArray(self, array: List[List[int]]) -> List[int]:\n",
    "        if not array: return []\n",
    "        l, r, t, b, res = 0, len(array[0]) - 1, 0, len(array) - 1, []\n",
    "        while True:\n",
    "            for i in range(l, r + 1): res.append(array[t][i]) # left to right\n",
    "            t += 1\n",
    "            if t > b: break\n",
    "            for i in range(t, b + 1): res.append(array[i][r]) # top to bottom\n",
    "            r -= 1\n",
    "            if l > r: break\n",
    "            for i in range(r, l - 1, -1): res.append(array[b][i]) # right to left\n",
    "            b -= 1\n",
    "            if t > b: break\n",
    "            for i in range(b, t - 1, -1): res.append(array[i][l]) # bottom to top\n",
    "            l += 1\n",
    "            if l > r: break\n",
    "        return res\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def spiralArray(self, array: List[List[int]]) -> List[int]:\n",
    "        res = []\n",
    "        if len(array) == 0 or len(array[0]) == 0:\n",
    "            return res\n",
    "        m = len(array)\n",
    "        n = len(array[0])\n",
    "        upper = 0\n",
    "        lower = m-1\n",
    "        left = 0\n",
    "        right = n-1\n",
    "        while upper <= lower and left <= right:\n",
    "            for a in range(left, right+1):\n",
    "                res.append(array[upper][a])\n",
    "            for b in range(upper+1, lower+1):\n",
    "                res.append(array[b][right])\n",
    "            if lower > upper:\n",
    "                for c in range(right-1, left-1, -1):\n",
    "                    res.append(array[lower][c])\n",
    "            if right > left:\n",
    "                for d in range(lower-1, upper, -1):\n",
    "                    res.append(array[d][left])\n",
    "            upper += 1\n",
    "            lower -= 1\n",
    "            left += 1\n",
    "            right -= 1\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def spiralArray(self, array: List[List[int]]) -> List[int]:\n",
    "        # direction = ((0,1),(0,-1),(1,0),(-1,0))\n",
    "        if not array: return []\n",
    "        l, r, t, b, res = 0, len(array[0]) - 1, 0, len(array) - 1, []\n",
    "        while True:\n",
    "            for i in range(l, r + 1): res.append(array[t][i]) # left to right\n",
    "            t += 1\n",
    "            if t > b: break\n",
    "            for i in range(t, b + 1): res.append(array[i][r]) # top to bottom\n",
    "            r -= 1\n",
    "            if l > r: break\n",
    "            for i in range(r, l - 1, -1): res.append(array[b][i]) # right to left\n",
    "            b -= 1\n",
    "            if t > b: break\n",
    "            for i in range(b, t - 1, -1): res.append(array[i][l]) # bottom to top\n",
    "            l += 1\n",
    "            if l > r: break\n",
    "        return res\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def spiralArray(self, array: List[List[int]]) -> List[int]:\n",
    "        if not array: return []\n",
    "        l, r, t, b, res = 0, len(array[0]) - 1, 0, len(array) - 1, []\n",
    "        while True:\n",
    "            for i in range(l, r + 1): res.append(array[t][i]) # left to right\n",
    "            t += 1\n",
    "            if t > b: break\n",
    "            for i in range(t, b + 1): res.append(array[i][r]) # top to bottom\n",
    "            r -= 1\n",
    "            if l > r: break\n",
    "            for i in range(r, l - 1, -1): res.append(array[b][i]) # right to left\n",
    "            b -= 1\n",
    "            if t > b: break\n",
    "            for i in range(b, t - 1, -1): res.append(array[i][l]) # bottom to top\n",
    "            l += 1\n",
    "            if l > r: break\n",
    "        return res\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def spiralArray(self, array: List[List[int]]) -> List[int]:\n",
    "        m=len(array)\n",
    "        if(m==0):\n",
    "            return []\n",
    "        n=len(array[0])\n",
    "        left,up=0,0\n",
    "        right=n-1\n",
    "        down=m-1\n",
    "        count=[]\n",
    "        if(n==0):\n",
    "            return []\n",
    "        while(True):\n",
    "            for i in range(left,right+1):\n",
    "                count.append(array[up][i])\n",
    "            up+=1\n",
    "            if(up>down):\n",
    "                break\n",
    "\n",
    "            for i in range(up,down+1):\n",
    "                count.append(array[i][right])\n",
    "            right-=1\n",
    "            if(right<left):\n",
    "                break\n",
    "\n",
    "            for i in range(right,left-1,-1):\n",
    "                count.append(array[down][i])\n",
    "            down-=1\n",
    "            if(down<up):\n",
    "                break\n",
    "\n",
    "            for i in range(down,up-1,-1):\n",
    "                count.append(array[i][left])\n",
    "            left+=1\n",
    "            if(left>right):\n",
    "                break\n",
    "        return count"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def spiralArray(self, array: List[List[int]]) -> List[int]:\n",
    "        if not array or not array[0]:\n",
    "            return list()\n",
    "\n",
    "        rows, columns = len(array), len(array[0])\n",
    "        visited = [[False] * columns for _ in range(rows)]\n",
    "        total = rows * columns\n",
    "        order = [0] * total\n",
    "\n",
    "        directions = [[0, 1], [1, 0], [0, -1], [-1, 0]]\n",
    "        row, column = 0, 0\n",
    "        directionIndex = 0\n",
    "        for i in range(total):\n",
    "            order[i] = array[row][column]\n",
    "            visited[row][column] = True\n",
    "            nextRow, nextColumn = row + directions[directionIndex][0], column + directions[directionIndex][1]\n",
    "            if not (0 <= nextRow < rows and 0 <= nextColumn < columns and not visited[nextRow][nextColumn]):\n",
    "                directionIndex = (directionIndex + 1) % 4\n",
    "            row += directions[directionIndex][0]\n",
    "            column += directions[directionIndex][1]\n",
    "        return order"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def spiralArray(self, array: List[List[int]]) -> List[int]:\n",
    "        if not array: return []\n",
    "        l, r, t, b, res = 0, len(array[0]) - 1, 0, len(array) - 1, []\n",
    "        while True:\n",
    "            for i in range(l, r + 1): res.append(array[t][i]) # left to right\n",
    "            t += 1\n",
    "            if t > b: break\n",
    "            for i in range(t, b + 1): res.append(array[i][r]) # top to bottom\n",
    "            r -= 1\n",
    "            if l > r: break\n",
    "            for i in range(r, l - 1, -1): res.append(array[b][i]) # right to left\n",
    "            b -= 1\n",
    "            if t > b: break\n",
    "            for i in range(b, t - 1, -1): res.append(array[i][l]) # bottom to top\n",
    "            l += 1\n",
    "            if l > r: break\n",
    "        return res\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def spiralArray(self, array: List[List[int]]) -> List[int]:\n",
    "        if not array:return []\n",
    "        t,r,b,l,res=0,len(array[0])-1,len(array)-1,0,[]\n",
    "        while True:\n",
    "            for i in range(l,r+1):\n",
    "                res.append(array[t][i])\n",
    "            t=t+1\n",
    "            if t>b: break\n",
    "            for i in range(t,b+1):\n",
    "                res.append(array[i][r])\n",
    "            r=r-1\n",
    "            if l>r: break\n",
    "            for i in range(r,l-1,-1):\n",
    "                res.append(array[b][i])\n",
    "            b=b-1\n",
    "            if t>b: break\n",
    "            for i in range(b,t-1,-1):\n",
    "                res.append(array[i][l])\n",
    "            l=l+1\n",
    "            if l>r: break\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def spiralArray(self, array: List[List[int]]) -> List[int]:\n",
    "        if not array:\n",
    "            return array\n",
    "        m = len(array)\n",
    "        n = len(array[0])\n",
    "        ans = []\n",
    "        l,r,t,b=0,n-1,0,m-1\n",
    "        while True:\n",
    "            for j in range(l, r+1):\n",
    "                ans.append(array[t][j])\n",
    "            t += 1\n",
    "            if t > b:\n",
    "                break\n",
    "            for i in range(t, b+1):\n",
    "                ans.append(array[i][r])\n",
    "            r -= 1\n",
    "            if r < l:\n",
    "                break\n",
    "            for j in range(r, l-1, -1):\n",
    "                ans.append(array[b][j])\n",
    "            b -= 1\n",
    "            if b < t:\n",
    "                break\n",
    "            for i in range(b, t-1, -1):\n",
    "                ans.append(array[i][l])\n",
    "            l += 1\n",
    "            if r < l:\n",
    "                break\n",
    "        return ans\n",
    "            \n",
    "            \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def spiralArray(self, array: List[List[int]]) -> List[int]:\n",
    "        matrix=array\n",
    "        if not matrix or not matrix[0]:\n",
    "            return []\n",
    "        l,r,u,d = 0, len(matrix[0])-1, 0, len(matrix)-1\n",
    "        res = []\n",
    "        size = (r+1) * (d+1)\n",
    "        while len(res)<size:\n",
    "            res.extend(matrix[u][l:r+1])\n",
    "            u+=1\n",
    "        \n",
    "            for point in range(u,d+1):\n",
    "                res.append(matrix[point][r])\n",
    "            r-=1\n",
    "            if len(res)>=size:\n",
    "                break\n",
    "            res.extend(reversed(matrix[d][l:r+1]))\n",
    "            d-=1           \n",
    "\n",
    "            for point in range(d,u-1,-1):\n",
    "                res.append(matrix[point][l])\n",
    "            l+=1\n",
    "        return res "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def spiralArray(self, array: List[List[int]]) -> List[int]:\n",
    "        if array == []:\n",
    "            return []\n",
    "\n",
    "        startx = 0\n",
    "        starty = 0\n",
    "        \n",
    "        lenx = len(array)\n",
    "        leny = len(array[0])\n",
    "\n",
    "        loop = min(lenx,leny) // 2\n",
    "\n",
    "        ans = []\n",
    "\n",
    "        for offset in range(1, loop+1):\n",
    "            for i in range(starty, leny-offset):\n",
    "                ans.append(array[startx][i])\n",
    "\n",
    "            for i in range(startx, lenx-offset):\n",
    "                ans.append(array[i][leny-offset])\n",
    "            \n",
    "            for i in range(leny-offset,starty, -1):\n",
    "                ans.append(array[lenx-offset][i])\n",
    "            \n",
    "            for i in range(lenx-offset, startx, -1):\n",
    "                ans.append(array[i][starty])\n",
    "\n",
    "            startx += 1\n",
    "            starty += 1\n",
    "\n",
    "\n",
    "        if lenx % 2 != 0 and lenx <= leny:  # x比y小 并且是奇数行，需要补中间一行\n",
    "            need = lenx * leny - len(ans)\n",
    "            for i in range(need):\n",
    "                ans.append(array[startx][starty+i])\n",
    "\n",
    "        if leny % 2 != 0 and lenx > leny:  # y比x小 并且是奇数列，需要补中间一列\n",
    "            need = lenx * leny - len(ans)\n",
    "            for i in range(need):\n",
    "                ans.append(array[startx+i][starty])\n",
    "\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def spiralArray(self, array: List[List[int]]) -> List[int]:\n",
    "        res=[]\n",
    "        if not array:\n",
    "            return res\n",
    "        x=len(array)\n",
    "        y=len(array[0])\n",
    "        # 只有一行\n",
    "        if x==1:\n",
    "            return array[0]\n",
    "        # 左右上下\n",
    "        left,right,top,bottom=0,y-1,0,x-1\n",
    "        while left<=right and top<=bottom:\n",
    "            # 从上到下，加一行\n",
    "            if top<=bottom:\n",
    "                res.extend(array[top][left:right+1])\n",
    "                top+=1\n",
    "            #加矩形右边元素\n",
    "            if left<=right:\n",
    "                for a in array[top:bottom+1]:\n",
    "                    # 取右边的值，每行遍历 每个 a列表，取 right 索引的值。\n",
    "                    res.append(a[right])\n",
    "                right-=1\n",
    "            # 从右向左，加横行元素\n",
    "            if bottom>=top:\n",
    "                # 横着，逆序加\n",
    "                for i in range(right,left-1,-1):\n",
    "                    # bottom,处理底下的行，索引是 i\n",
    "                    res.append(array[bottom][i])\n",
    "                bottom-=1\n",
    "            # 从下往上加，left 元素\n",
    "            if left<=right:\n",
    "                for a in range(bottom,top-1,-1):\n",
    "                    # a变化，每行的位置，left 固定\n",
    "                    res.append(array[a][left])\n",
    "                left+=1\n",
    "        print(res)\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def spiralArray(self, array: List[List[int]]) -> List[int]:\n",
    "        if array == []:\n",
    "            return []\n",
    "        l, r, t, b, res = 0, len(array[0]) - 1, len(array) - 1, 0, []\n",
    "        while True:\n",
    "            for i in range(l, r + 1):\n",
    "                res.append(array[b][i])\n",
    "            b += 1\n",
    "            if t < b: break\n",
    "            for i in range(b, t + 1):\n",
    "                res.append(array[i][r])\n",
    "            r -= 1\n",
    "            if r < l: break\n",
    "            for i in range(r, l - 1, -1):\n",
    "                res.append(array[t][i])\n",
    "            t -= 1\n",
    "            if t < b: break\n",
    "            for i in range(t, b - 1, -1):\n",
    "                res.append(array[i][l])\n",
    "            l += 1\n",
    "            if r < l: break\n",
    "        return res\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def spiralArray(self, array: List[ List[ int ] ]) -> List[ int ]:\n",
    "        # 0 右 1 下 2 左 3 上\n",
    "        result = [ ]\n",
    "\n",
    "        def doFuc(func, c, nex) -> (int, int):\n",
    "            if c == 4:\n",
    "                return None\n",
    "            if func == 0:\n",
    "                next1 = (nex[ 0 ], nex[ 1 ] + 1)\n",
    "            elif func == 1:\n",
    "                next1 = (nex[ 0 ] + 1, nex[ 1 ])\n",
    "            elif func == 2:\n",
    "                next1 = (nex[ 0 ], nex[ 1 ] - 1)\n",
    "            elif func == 3:\n",
    "                next1 = (nex[ 0 ] - 1, nex[ 1 ])\n",
    "            if next1[ 0 ] < 0 or next1[ 0 ] == len(array) or next1[ 1 ] < 0 or next1[ 1 ] == len(array[ 0 ]):\n",
    "                return doFuc((func + 1) % 4, c + 1, nex)\n",
    "            if array[ next1[ 0 ] ][ next1[ 1 ] ] == None:\n",
    "                return doFuc((func + 1) % 4, c + 1, nex)\n",
    "            return func, next1\n",
    "\n",
    "        res = doFuc(0, 0, (0, -1))\n",
    "        while res is not None:\n",
    "            result.append(array[ res[ 1 ][ 0 ]][ res[ 1 ][ 1 ] ] )\n",
    "            array[ res[ 1 ][ 0 ] ][ res[ 1 ][ 1 ] ] = None\n",
    "            res = doFuc(res[ 0 ], 0, res[ 1 ])\n",
    "\n",
    "        return result"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def spiralArray(self, array: List[List[int]]) -> List[int]:\n",
    "        res = []\n",
    "        while array:\n",
    "            res += array.pop(0)\n",
    "            array = list(zip(*array))[::-1]\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def spiralArray(self, matrix: List[List[int]]) -> List[int]:\n",
    "        m = len(matrix)\n",
    "        if m==0:\n",
    "            return []\n",
    "        n = len(matrix[0])\n",
    "        loop = m//2\n",
    "\n",
    "        ans = [0]*n*m\n",
    "        if m == 1:\n",
    "            for i in range(n):\n",
    "                ans[i] = matrix[0][i]\n",
    "        if n == 1:\n",
    "            for i in range(m):\n",
    "                ans[i] = matrix[i][0]\n",
    "        else:\n",
    "            x0,y0 = 0,0\n",
    "            # print(ans)\n",
    "            count = 0\n",
    "            for i in range(1,loop+1):\n",
    "                for j in range(x0,n-i):\n",
    "                    ans[count] = matrix[x0][j]\n",
    "                    count += 1\n",
    "                if count >= m*n:\n",
    "                    break\n",
    "                for j in range(y0,m-i):\n",
    "                    # print(j,n-i,count,m*n)\n",
    "                    ans[count] = matrix[j][n-i]\n",
    "                    count += 1\n",
    "                if count >= m*n:\n",
    "                    break\n",
    "                for j in range(n-i,y0,-1):\n",
    "                    ans[count] = matrix[m-i][j]\n",
    "                    count += 1\n",
    "                if count >= m*n:\n",
    "                    break\n",
    "                for j in range(m-i,x0,-1):\n",
    "                    print(j,y0,m-i,count,m*n)\n",
    "                    ans[count] = matrix[j][y0]\n",
    "                    count += 1\n",
    "                    if count >= m*n:\n",
    "                        break\n",
    "                if count >= m*n:\n",
    "                    break\n",
    "                x0 += 1\n",
    "                y0 += 1\n",
    "            if m%2 != 0 and count<m*n:\n",
    "                mid = m//2\n",
    "                for j in range(x0,n-loop):\n",
    "                    ans[count] = matrix[x0][j]\n",
    "                    count += 1\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def spiralArray(self, array: List[List[int]]) -> List[int]:\n",
    "        result=[]\n",
    "        while array:\n",
    "            result.extend(array.pop(0))\n",
    "            array=list(zip(*array))[::-1]\n",
    "        \n",
    "\n",
    "        return result\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def spiralArray(self, matrix: List[List[int]]) -> List[int]:\n",
    "        res = []\n",
    "        while matrix:\n",
    "            res += matrix.pop(0)\n",
    "            matrix = list(zip(*matrix))[::-1]\n",
    "        return res\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def spiralArray(self, arr: List[List[int]]) -> List[int]:\n",
    "        res = []\n",
    "        while arr:\n",
    "            res += arr.pop(0)\n",
    "            arr = list(zip(*arr))[::-1]\n",
    "        return res\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def spiralArray(self, array1: List[List[int]]) -> List[int]:\n",
    "        a = []\n",
    "        while array1:\n",
    "            a += array1.pop(0)\n",
    "            array1 = list(zip(*array1))[::-1]\n",
    "        return a"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def spiralArray(self, array: List[List[int]]) -> List[int]:\n",
    "        res = []\n",
    "        while array:\n",
    "            res += array.pop(0)\n",
    "            array = list(zip(*array))[:: -1]\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def spiralArray(self, array: List[List[int]]) -> List[int]:\n",
    "        res = []\n",
    "        while len(array) > 0:\n",
    "            res += array.pop(0)\n",
    "            array = list(map(list, zip(*array)))[::-1]\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def spiralArray(self, array: List[List[int]]) -> List[int]:\n",
    "        ans = []\n",
    "        while array:\n",
    "            ans += array.pop(0)\n",
    "            array = list(zip(*array))[::-1]\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def spiralArray(self, array: List[List[int]]) -> List[int]:\n",
    "        nums = []\n",
    "        while array:\n",
    "            nums += array.pop(0)\n",
    "            array = list(zip(*array))[::-1]\n",
    "        return nums"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def spiralArray(self, array: List[List[int]]) -> List[int]:\n",
    "        ans = []\n",
    "        while array:\n",
    "            ans += array.pop(0)\n",
    "            array = list(zip(*array))[::-1]\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def spiralArray(self, array1: List[List[int]]) -> List[int]:\n",
    "        a = []\n",
    "        while array1:\n",
    "            a += array1.pop(0)\n",
    "            array1 = list(zip(*array1))[::-1]\n",
    "        return a"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def spiralArray(self, array: List[List[int]]) -> List[int]:\n",
    "        res = []\n",
    "        while array:\n",
    "            # 削头（第一层）\n",
    "            res += array.pop(0)\n",
    "            # 将剩下的逆时针转九十度，等待下次被削\n",
    "            array = list(zip(*array))[::-1]\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def spiralArray(self, array1: List[List[int]]) -> List[int]:\n",
    "        a = []\n",
    "        while array1:\n",
    "            a += array1.pop(0)\n",
    "            array1 = list(zip(*array1))[::-1]\n",
    "        return a"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def spiralArray(self, array: List[List[int]]) -> List[int]:\n",
    "        if not array or not array[0]:\n",
    "            return []\n",
    "        direction = [[0,1],[1,0],[0,-1],[-1,0]]\n",
    "        x,y = 0,0\n",
    "        m = len(array)\n",
    "        n = len(array[0])\n",
    "        l = m * n\n",
    "        num = 0\n",
    "        visited = [[False]*n for _ in range(m)]\n",
    "        ans = []\n",
    "        for i in range(l):\n",
    "            ans.append(array[x][y])\n",
    "            x_next = x + direction[num][0]\n",
    "            y_next = y + direction[num][1]\n",
    "            print(x,y,x_next,y_next)\n",
    "            if x_next < 0 or x_next >= m or y_next < 0 or y_next >= n or visited[x_next][y_next]:\n",
    "                num += 1\n",
    "            num = num % 4\n",
    "            visited[x][y] = True\n",
    "            x += direction[num][0]\n",
    "            y += direction[num][1]\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def spiralArray(self, array: List[List[int]]) -> List[int]:\n",
    "        res = []\n",
    "        while array:\n",
    "            res += array.pop(0)\n",
    "            array = list(zip(*array))[::-1]\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def spiralArray(self, array: List[List[int]]) -> List[int]:\n",
    "        \n",
    "        al = []\n",
    "        \n",
    "        while array:\n",
    "            al += array[0]\n",
    "            del array[0]\n",
    "            array[:] = zip(*array)\n",
    "            array = array[::-1]\n",
    "            \n",
    "        return al"
   ]
  }
 ],
 "metadata": {},
 "nbformat": 4,
 "nbformat_minor": 2
}
